// https://leetcode.cn/problems/beautiful-arrangement/description/

// 算法思路总结：
// 1. 回溯算法统计优美排列的数量
// 2. 每个位置i的数字必须满足：i整除数字 或 数字整除i
// 3. 使用vis数组避免数字重复选择
// 4. perm[0]作为哨兵位，实际排列从perm[1]开始
// 5. 时间复杂度：O(k)，空间复杂度：O(n)

#include <iostream>
using namespace std;

#include <cstring>
#include <vector>
#include <algorithm>

class Solution 
{
public:
    vector<int> perm;
    int ret, _n;
    bool vis[17] = {false};
    int countArrangement(int n) 
    {
        ret = 0;
        _n = n;
        perm.push_back(0);
        memset(vis, 0, sizeof(vis));

        dfs();

        return ret;
    }

    void dfs()
    {
        if (perm.size() == _n + 1)
        {
            ret++;
            return ;
        }
        
        for (int i = 1 ; i <= _n ; i++)
        {
            if (vis[i] == false && (i % perm.size() == 0 || perm.size() % i == 0))
            {
                perm.push_back(i);
                vis[i] = true;
                dfs();
                perm.pop_back();
                vis[i] = false;
            }
        }
    }
};

int main()
{
    int n1 = 2, n2 = 1;
    Solution sol;

    cout << sol.countArrangement(n1) << endl;
    cout << sol.countArrangement(n2) << endl;

    return 0;
}